package william.list;

import java.util.List;

/**
 * @author ZhangShenao
 * @date 2024/3/13
 * @description <a href="https://leetcode.cn/problems/sort-list/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 */
public class Leetcode148_排序链表 {
    private class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 基于递归,实现自顶向下的归并排序
     * 针对一个有序链表[head,tail)范围
     * 首先通过快慢指针法,找到中间节点mid
     * 然后分别对[head,mid)和[mid,tail)两个链表进行递归的归并排序
     * 最后将两个有序链表合并成一个整体有序链表
     * <p>
     * 时间复杂度O(N*logN) 归并排序的复杂度
     * 空间复杂度O(logN) 递归栈空间
     */
    public ListNode sortList(ListNode head) {
        //边界条件校验
        if (head == null) {
            return head;
        }

        //调用递归实现
        return mergeSortList(head, null);
    }

    /**
     * 递归实现
     * 对链表[head,tail)范围进行归并排序,返回排好序的链表头节点
     */
    private ListNode mergeSortList(ListNode head, ListNode tail) {
        //递归终止条件:范围内仅剩一个节点
        if (head == null) {
            return head;
        }
        if (head.next == tail) {
            head.next = null;   //切断原始链表,避免成环
            return head;
        }

        //通过快慢指针法,找到[head,tail)链表的中点
        ListNode fast = head;
        ListNode slow = head;
        while (fast != tail) {
            fast = fast.next;
            slow = slow.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }

        //slow节点指向链表中点
        //对链表[head,mid)和[mid,tail)两部分分别递归进行归并排序
        ListNode l = mergeSortList(head, slow);
        ListNode r = mergeSortList(slow, tail);

        //将两个链表有序链表合并成一个整体有序链表
        ListNode merged = merge(l, r);

        //返回合并后的头节点
        return merged;

    }

    /**
     * 将两个有序链表l和r合并成一个整体有序链表
     */
    private ListNode merge(ListNode l, ListNode r) {
        //创建哑头节点
        ListNode dummy = new ListNode();
        ListNode merged = dummy;

        //同时遍历两个有序链表,将较小的节点追加的新链表末尾,并向后移动
        while (l != null && r != null) {
            if (l.val <= r.val) {
                merged.next = l;
                l = l.next;
            } else {
                merged.next = r;
                r = r.next;
            }
            merged = merged.next;
        }

        //处理还剩余一个链表的情况
        if (l != null) {
            merged.next = l;
        }
        if (r != null) {
            merged.next = r;
        }


        //返回合并后的头节点
        return dummy.next;
    }
}
